package com.it.od.csdn200;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 项目排期
 * 输入
 * 第一行:需求工作量
 * 第二行:人数
 * 6 2 7 7 9 3 2 1 3 11 4
 * 2
 * 输出:最短完工时间
 * 28
 */

public class Main12 {
    public static void main(String[] args) {
        // 使用Scanner读取输入
        Scanner scanner = new Scanner(System.in);
        // 读取第一行输入，即需求的工作量，并以空格分隔
        String[] workloads = scanner.nextLine().split(" ");
        // 读取第二行输入，即项目组人员数量
        int N = Integer.parseInt(scanner.nextLine());
        // 创建一个数组来存放每个需求的工作量
        Integer[] tasks = new Integer[workloads.length];

        // 将输入的工作量转换为整数并存入数组
        for (int i = 0; i < workloads.length; i++) {
            tasks[i] = Integer.parseInt(workloads[i]);
        }

        // 输出最快完成所有工作的天数
        System.out.println(minimumTimeRequired(tasks, N));
    }

    // 计算完成所有任务所需的最少天数
    public static int minimumTimeRequired(Integer[] tasks, int k) {
        // 将任务按工作量降序
        Arrays.sort(tasks, (o1, o2) -> o2 - o1);

        // 使用二分查找确定完成所有任务的最短时间
        int l = tasks[0], r = Arrays.stream(tasks).reduce(Integer::sum).get();
        while (l < r) {
            int mid = (l + r) / 2;
            // 检查当前时间限制是否足够完成所有任务
            if (canFinish(tasks, k, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        // 返回最短完成时间
        return l;
    }

    // 检查是否可以在给定的时间限制内完成所有任务
    private static boolean canFinish(Integer[] tasks, int k, int limit) {
        // 创建一个数组来记录每个员工的工作量
        int[] workers = new int[k];
        // 使用回溯法检查是否可以完成
        return backtrack(tasks, workers, 0, limit);
    }

    // 回溯法
    private static boolean backtrack(Integer[] tasks, int[] workers, int index, int limit) {
        // 如果所有任务都已分配，则返回true
        if (index >= tasks.length) {
            return true;
        }

        // 获取当前任务的工作量
        int current = tasks[index];
        // 尝试将当前任务分配给每个员工
        for (int i = 0; i < workers.length; i++) {
            // 如果当前员工可以在时间限制内完成这项任务
            if (workers[i] + current <= limit) {
                // 分配任务给当前员工
                workers[i] += current;
                // 继续尝试分配下一个任务
                if (backtrack(tasks, workers, index + 1, limit)) {
                    return true;
                }
                // 回溯，取消当前的任务分配
                workers[i] -= current;
            }

            // 如果当前员工没有任务或者加上当前任务刚好达到时间限制，则不需要尝试其他员工
            if (workers[i] == 0 || workers[i] + current == limit) {
                break;
            }
        }

        // 如果无法分配当前任务，则返回false
        return false;
    }
}
